/*
 * @lc app=leetcode id=230 lang=cpp
 *
 * [230] Kth Smallest Element in a BST
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    deque<TreeNode*> dq;
public:
    
    int kthSmallest(TreeNode* root, int k) {

        TreeNode *node = root;
        bool visited = false;
        while(1) {
            while(!visited && node->left) {
                dq.push_back(node);
                node = node->left;
            }

            if (--k == 0) {
                return node->val;
            } else if (node->right) {
                node = node->right;
                visited = false;
            } else if (!dq.empty()){
                node = dq.back();
                dq.pop_back();
                visited = true;
            } else {
                break;
            }
        }
        return -1;
        
    }
};

